\subsection*{Heterogeneous seeds and heterogeneous lookup table}

Using longer seeds can be considered as extending short seeds with more bases, i.e.
adding bases trailing to the short seeds to make them longer. Extending short
seeds generates more permutations. For each single base added to a short seed,
there will be four new permutations as the extended base can be any of A, C, G
and T. The four new permutations partition and inherit the locations of the
original short seed, each taking a portion of it.

The seed extension can also be visualized in the form of a tree.  Consider a
tree where each node represents a seed at a certain length, as the tree in
Figure~\ref{fig:ExtTree}, and its four children represent the extensions with
one more base extended to it---A, C, G and T respectively, denoted by edge
label. The root node of the tree is one of the short expensive seeds.

Previous works have used seeds of a uniform length throughout the mapping
process (e.g seeds of length 12 in mrFAST, seeds of length 20 in SNAP). We call
such seeds as \textbf{homogeneous seeds}. Using longer seeds can be viewed as
extending homogeneous short seeds uniformly to homogeneous long seeds.

While extending both cheap seeds and expensive seeds generate the same number of
new permutations, according to Equation~\ref{eq:map_cost_2}, extending a cheap
seed provides little reduction in mapping cost. As a result, we conclude that
only expensive seeds should be extended into longer seeds while the extension
should stop as soon as the extended long seeds becomes cheap.

%Although extending a short seed definitely reduces the total mapping cost,
%the reduction of mapping cost of different extensions on different short seeds
%varies quite drastically. On the contrary, no matter what short seed it is, all
%extensions consume the same amount of memory regardless of how much reduction in
%mapping cost they provide. Based on this observation, we conclude that
%short seeds that are expensive, 
%while at the same time distribute their locations evenly into its
%children extended seeds can provide the most reduction of mapping cost through
%extension.
%
%Extending a short seed provides substantial reduction of mapping cost only if the
%original short seed is expensive. When locations are
%distributed evenly into children extended seeds, extending a short seed by one base
% achieves the maximum reduction of mapping cost by 3/4 of the
%mapping cost of the original short seed. For a cheap short seed, its original
%mapping cost is already very small. Hence extending a cheap seed does not provide
%much reduction in total mapping cost of the entire lookup table. For instance,
%assume that seed $\alpha$ has 4 locations and also distributes its locations evenly into its
%four extensions. The reduction of mapping cost of $\alpha$ would be
%$\frac{16}{C} - 4 \times \frac{1}{C} = \frac{12}{C}$. Similarly, assume that another seed $\beta$ has
%4000 locations and also distributes its locations evenly into its four
%extensions. The reduction of $\beta$ would be $\frac{12000000}{C}$, a million
%times more than that of seed $\alpha$, even though the added memory consumption of extending both
%seeds are the same, which is four permutations. As a result, we conclude that we
%should only extend expensive short seeds to longer seeds.

\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{figures/ExtTree_B.pdf}
\caption{An extension tree of the expensive short seed ``TCTTTCCTTTCT''. Each
node in the tree represents an extended longer seed of ``TCTTTCCTTTCT''. The
number in each node represents the total number of locations in each seed. The
leaf nodes in the extension tree are the seeds having fewer than 100 locations,
i.e, the cheap seeds.}
\label{fig:ExtTree}
\end{figure}


The extension strategy is best described as the extension tree shown in
Figure~\ref{fig:ExtTree}. With a preset threshold $\tau$, we define seeds with a
number of locations greater than $\tau$ as \textbf{expensive seeds}, whereas seeds
with a number of locations smaller than $\tau$ are \textbf{cheap seeds}. In
this paper, we choose a threshold $\tau = 100$ (effects of choosing other
thresholds are explored in the "Analysis" section). Figure~\ref{fig:ExtTree}
represents an extension tree of a basic seed ``TCTTTCCTTTCT". As the figure
shows, we keep extending the seed into longer seeds until the extended long
seed comes a cheap seed, which is a leaf node of the tree. We stop further
extending the seed when the seed becomes cheap since it is no longer cost
efficient as we prove above.  After we have extended the seed into all leaf
nodes, we have reached a point where the expensive short seed has been
efficiently extended into many long seeds at different lengths and the
locations of the expensive short seeds are also evenly distributed among all
long seeds.

\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{figures/LookupExt_B.pdf}
\caption{The heterogeneous lookup table. While the entries of cheap
short seeds are left unmodified, the entries of expensive short
seeds are extended into extension tables, which host
extensions of the expensive seeds and their locations. Notice that no extended
long seeds are expensive in the extension table (until the extension reaches
the maximum length $L_{max}$).
}
\label{fig:LookupExt}
\end{figure}

With the help of the extension tree, we now revise the lookup table of
homogeneous short seeds to enable extension for the expensive short seeds. We call
this data structure ``heterogeneous lookup table". The data structure is shown
in Figure~\ref{fig:LookupExt}.  On top of the original ``seed $\rightarrow$
locations" permutation array, we add a key-value table, which is called
\textbf{extension table}, to store the extensions of the expensive
short seeds. The keys in the extension table are different extensions of an expensive
short seed while the values are locations of the extended long seeds.

Ideally, we would like to keep extending the short seeds until all seeds are
cheap. However, as we will describe later, allowing seeds to extend infinitely
reduces the error-tolerance of the mapper. In this paper, we impose a maximum
limit of seed length $L_{max} = 24$ (effects of choosing other
maximum lengths are explored in the "Analysis" section). No seed in the heterogeneous lookup table is
longer than this limit.

At mapping, a long seed with the length of $L_{max}$ is sent to the lookup
table for its locations. The seed is first divided into 2 sub-sequences: a head
sequence with the same length of the short seeds which is called the
``\textbf{basic part}" while the rest of the seed is called the
``\textbf{extension part}". Basic part is used to query the permutation array.
If the entry of the basic part is a cheap short seed, then no further extension
is required and all locations of the cheap short seed is returned. If the entry
of the basic part is an expensive short seed which has a pointer to an
extension table in the permutation array, then the extension part is used to
search for the potential matching in the extension table. Once the mapper found the
matching extension, all locations of the extended long cheap seed are returned to the mapper.

%% CALKAN: is the permutation array the same thing with the original hash table?
%With heterogeneous lookup table, we can simulate using long seeds without 
%a large memory overhead. When we have a long seed that is twice as long as the
%basic seed, we first divide the long seed into two halves. We define the first
%half as the ``\textbf{basic part}" while the second half as the
%``\textbf{extension part}". We first use the basic part to index the permutation
%array, which can be directly accessed. If the basic part of the long seed matches an
%expensive basic seed in the permutation array, then we use the extension part to
%search in the extension table for a matching extension, which returns the
%locations of the long seed. If the basic part of the long seed is a cheap basic
%seed, then we no long need the extension part since the basic part of the seed
%is a cheap seed and extending a cheap seed does not payoff.
%
%If the basic part of a long seed matches a cheap basic seed in the heterogeneous
%lookup table, the lookup time of the seed will be the same with the lookup time
%of homogeneous short seeds. If the basic part of the long seed matches an
%expansive basic seed, we perform an extra binary search in the extension
%table that slightly slows down the lookup time. Fortunately, most expensive
%short seeds have very few extensions (over 90\% of the expensive basic seeds
%have fewer than 32 extensions in human chromosome 1). Even for the most
%expensive short seed, the number is manageable (the most expensive short seed in
%human chromosome 1 has XXX extensions). Considering that binary search is
%$O(Log_{2}(N))$, where N is the number of extensions, the slow down of
%lookup time will be negligible.
%
%The memory consumption of heterogeneous lookup table is only slightly higher
%than the lookup table of homogeneous short seeds. Since we only extend
%expensive short seeds (less than 0.9\% of the seeds are expensive seeds in the
%human chromosome 1), and stops whenever an extension becomes cheap, the
%total number of extensions is marginal compared to the total number of short seeds. We found
%a total of 1833379 extensions in our simulation study, which is around 10\% of
%the total short seeds at length 12.
